#include <iostream>
#include <stdio.h>

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>

class Solution {
private:
    std::unordered_map<std::string, std::map<std::string,int>> targets;
    bool backtracking (int ticketNum, std::vector<std::string>& result) {
        if(result.size() == ticketNum +1){
            return true;
        }

        for (std::pair<const std::string, int>& target:targets[result[result.size()-1]]) {
            if(target.second > 0){
                result.push_back(target.first);
                target.second--;
                if(backtracking(ticketNum, result)) return true;
                result.pop_back();
                target.second++; 
            }
            
        }
        return false;
    }

public:
    std::vector<std::string> findItinerary(std::vector<std::vector<std::string>>& tickets) {
        targets.clear();
        std::vector<std::string> result;
        for (const std::vector<std::string>& vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

int main(int argv, char**argc)
{

    printf("************  test hello zc!!!   **************\n");
    /* add test code! */
    Solution solve;
    std::vector<std::string> ret;
    std::vector<std::vector<std::string>> vec = {{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}};
    ret = solve.findItinerary(vec);
    printf("[ ");
    for(auto p:ret){
        printf("[");
        printf("%s ", p.c_str());
        // for(auto q:p){
        //     printf("%d ", q);
        // }
        printf("] \n");    
    }
    printf("]\n");
    return 0;
}
